package com.itzmn.datastructure.sort;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/9 13:08
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:  希尔排序
 *
 *  思路：
 *      加强版的直接插入排序，直接插入排序是将数据和前面一个一个比较，次数较多
 *      希尔排序，是先将数据分组，然后将每组内的数据排序，然后将组数增多，在将每个组内的数据排序
 */
public class ShellSort {


    public static void main(String[] args) {
        int[] ints = {5,2,4,6,3,7,1};
        long l = System.currentTimeMillis();
        new ShellSort().shellSort(ints);
        System.out.println(System.currentTimeMillis()-l);
    }
    public void shellSort(int arrs[]){
        if (arrs.length==0){
            return;
        }
        //第一次设置增量为数组长度的一半
        int incrementNum = arrs.length/2;

        while (incrementNum >= 1){
            for (int i=0;i<arrs.length;i++){
                //对数据进行插入排序
                for (int j=i;j<arrs.length;j+=incrementNum){
                    int tem = arrs[j];
                    int m = j;
                    while (m-incrementNum>=0 && arrs[m]<arrs[m-incrementNum]){
                        arrs[m] = arrs[m-incrementNum];
                        m-=incrementNum;
                    }
                    if (m!=j){
                        arrs[m] = tem;
                    }
                }
            }
            incrementNum /=2;
        }

        log(arrs);


    }

    public void log(int arrs[]){

        for (int i=0;i<arrs.length;i++){
            System.out.print(arrs[i]+" ");
        }
        System.out.println();
    }


}
